package iks.utils.geom 
{
	import flash.geom.*;
	
	/**
	 * 给定起始点与结束点, 用Brensenham直线法找出其沿路的像素坐标集合
	 * @param	start 起始点
	 * @param	end 结束点
	 * @return 沿路的坐标点集合
	 */
	public function bresenhamLine(start : Point, end : Point) : Vector.<Point>
	{
		var path : Vector.<Point> = new Vector.<Point>();
		
		// 判断斜率是否超过1
		var steep : Boolean = Math.abs(end.y - start.y) > Math.abs(end.x - start.x);
		
		// 如果斜率大于1, 起始点与结束点各自的x, y轴互换;
		// ①: 这里保证dx总是大于dy的, 在之后的运算中保存路径点的时候再把x, y值互换回来
		if (steep)
		{
			start = new Point(Math.ceil(start.y), Math.ceil(start.x));
			end = new Point(Math.ceil(end.y), Math.ceil(end.x));
		}
		else
		{
			// 这里是创建起始点与结束点的副本, 不改变原来点的数据
			start = new Point(Math.ceil(start.x), Math.ceil(start.y));
			end = new Point(Math.ceil(end.x), Math.ceil(end.y));
		}
		
		// 判断起始点与结束点是否交换过
		var swapped : Boolean = false;
		
		// 让起始点的x坐标小于结束点的x坐标, 起始点与结束点互换
		// ②: 由于起始点和结束点相互改变了, 所以在计算完所有路径点之后, 颠倒一次路径数组, 恢复正常的路径顺序
		if (start.x > end.x)
		{
			var t : Number = start.x;
			start.x = end.x;
			end.x = t;
			
			t = start.y;
			start.y = end.y;
			end.y = t;
			
			swapped = true;
		}
		
		// 计算出差量
		var dx : int = end.x - start.x;
		var dy : int = Math.abs(end.y - start.y);
		
		// ③: 看计算机图形学, 一两句话说不清
		var e : int = dx / 2;
		
		// 计算y轴每次递增的增量
		var stepY : int = 0;
		if (start.y > end.y)
			stepY = -1;
		else
			stepY = 1;
		var y : int = start.y;
		
		for (var x : int = start.x; x <= end.x; ++x)
		{
			var pos : Point = null;
			
			// ①, 如果之前进行过互换操作, 这里将路径点互换回来
			if (steep)
				pos = new Point(y, x);
			else
				pos = new Point(x, y);
				
			path.push(pos);
			
			// ③: 看计算机图形学, 一两句话说不清
			e -= dy;
			if (e < 0)
			{
				e += dx;
				y += stepY;
			}
		}
		
		// ②, 如果之前改变过起始点与结束点, 这里将路径翻转以得到预期的路径
		if (swapped)
			path.reverse();
			
		return path;
	}

}

































///////////////////////////////////////////////////////////////////////////////////////////////////
// end file


